Random Early Detection (RED) is an algorithm for avoiding congestion in routers. It works on the assumption that a majority of traffic passing through a router comprises TCP (Transport Control Protocol) data packets sent from multiple users simultaneously sharing network resources.
According to TCP standards, a user transmits data packets to a destination node during an initial time window without receiving an acknowledgment. Typically, the size of the time window is increased in order to transmit data at successively higher rates. When experiencing congestion, a user will eventually receive feedback indicating that certain data packets generated during the TCP session have been dropped. In response to sensing dropped packets, TCP sessions reduce their window size and thus reduce their rate of sending traffic. This technique of adjusting a time window allows each user to transmit data at a corresponding peak data transfer rate.
Synchronization of many TCP sessions that increase their rate of transmitting data without receiving negative feedback (loss of data) can result in tremendous network congestion and lost data. This situation occurs when multiple users running separate TCP sessions simultaneously increase their rate of sending data.
To avoid this type of congestion, RED algorithms employ a technique of tracking an average queue length associated with a data queue in the router. Tracking of an average queue length metric allows the router to absorb short-term periods of congestion. For example, rather than allowing the queue to fill to its absolute capacity before dropping incoming data, RED randomly drops data packets according to a specified probability chart when the average queue length of data in the queue exceeds a threshold value indicating that the queue is quite full. Randomly dropping data packets in the flows at different times breaks the synchronization behavior.
The average queue length (AQL) metric associated with a queue has been tracked based on exponential weighted averaging of the instantaneous length of a queue, which indicates a relative fullness of the queue at a particular instant in time. For example, an exponentially weighted portion of the instantaneous queue length (IQL) metric is added to a previous AQL metric to produce a newly updated AQL metric. One conventional method of tracking queues specifically involves periodically updating an AQL metric of the queue at equally spaced intervals of time, while asynchronously updating an instantaneous queue length (IQL) metric associated with the queue at times when its contents are modified.